package com.leetcode.LC_MED;

import java.util.HashMap;

public class LC377 {
    public int rob(TreeNode root) {

        if (root == null) {
            return 0;
        }
        int sum = root.val;

        if (root.left != null) {
            sum += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            sum += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(sum, rob(root.left) + rob(root.right));
    }

    public int rob2(TreeNode root) {
        HashMap<TreeNode, Integer> memo = new HashMap<>();
        return roInternal(root, memo);

    }

    public int roInternal(TreeNode root, HashMap<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        int sum = root.val;
        if (root.left != null) {
            sum += roInternal(root.left.left, map) + roInternal(root.left.right, map);
        }
        if (root.right != null) {
            sum += roInternal(root.right.left, map) + roInternal(root.right.right, map);
        }
        int rs = Math.max(sum, roInternal(root.left, map) + roInternal(root.right, map));
        map.put(root, rs);
        return rs;
    }

}
